#include<iostream>
#include<algorithm>
#include<cstring>
#define ll long long
const int maxn=600000;
#define minn 1000000000
using namespace std;
struct node{
    int sum;
    int val;
    int rv;
    int lv;
};
node w[maxn*4];
ll a[maxn];
ll lazyj[maxn*4];
ll lazyc[maxn*4];
ll p;
inline void pushup(node & rt,const node & ls,const node & rs){
    if(ls.rv<0&&rs.lv<0){
        rt.val=max(ls.rv,rs.lv);
    }
    else {
        rt.val=0;
        if(ls.rv>0)rt.val+=ls.rv;
        if(rs.lv>0)rt.val+=rs.lv;
    }
    rt.val=max(rt.val,ls.val);
    rt.val=max(rt.val,rs.val);
    rt.lv=max(ls.lv,ls.sum+rs.lv);
    rt.rv=max(rs.rv,rs.sum+ls.rv);
    rt.sum=ls.sum+rs.sum;
}
void build(int u,int l,int r){
    if(l==r){
        w[u].sum=a[l];
        w[u].lv=a[l];
        w[u].rv=a[l];
        w[u].val=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(u*2,l,mid);
    build(u*2+1,mid+1,r);
    pushup(w[u],w[u<<1],w[u<<1|1]);
}
// int lazy[maxn*4];
// void maketag(ll u,ll l,ll r,ll x){
//     w[u].sum=(r-l+1)*x;
//     if(x>0){
//     w[u].lv=(r-l+1)*x;
//     w[u].rv=(r-l+1)*x;
//     w[u].val=(r-l+1)*x;
//     }
//     else{
//     w[u].lv=x;
//     w[u].rv=x;
//     w[u].val=x;
//     }
//     lazy[u]=x;
// }
// void pushdown(ll u,ll l,ll r){
//     ll mid=(l+r)>>1;
//     maketag(u*2,l,mid,lazy[u]);
//     maketag(u*2+1,mid+1,r,lazy[u]);
//     lazy[u]=0;
// }
bool inrange(int L, int R, int l, int r){
    return (L >= l) && (R <= r);
}

// 判断区间是否完全不包含
bool outrange(int L, int R, int l, int r){
    return (L > r) || (R < l);
}
void xg(ll u,ll L,ll R,ll mb,ll x){
    if(L==R){
        w[u].sum=w[u].val=w[u].lv=w[u].rv=x;
        return;
    }
    int m=(L+R)>>1;
    if(mb<=m)xg(u*2,L,m,mb,x);
    else{
        xg(u*2+1,m+1,R,mb,x);
    }
    pushup(w[u],w[u<<1],w[u<<1|1]);
}
node cx(int u, int L, int R, int l, int r){
    if (inrange(L, R, l, r)) return w[u];  // 完全包含的情况
    int mid=(L+R)>>1;
    if(l<=mid&&mid<r){
             node x;
             pushup(x,cx(u<<1,L,mid,l,r),cx(u<<1|1,mid+1,R,l,r));
             return x;
    }
 
    else if(l<=mid)return cx(u<<1,L,mid,l,r);
    else return cx(u<<1|1,mid+1,R,l,r);
    }
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    build(1,1,n);
    for(int i=1;i<=m;i++){
        int op;
        cin>>op;
        if(op==1){
            int a,b;
            cin>>a>>b;
            if(a>b)swap(a,b);
            cout<<cx(1,1,n,a,b).val<<endl;
        }
        if(op==2){
            int a,b;
            cin>>a>>b;
            xg(1,1,n,a,b);
        }
    }
    return 0;
}
